/*
题目: 少有 K 个重复字符的最长子串
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/
 */
public class LongestSubstring {
    public int longestSubstring(String s, int k) {
        // 分治: 对于字符串 s，如果存在某个字符 ch，它的出现次数大于 0 且小于 k，则任何包含 ch 的子串都不可能满足要求
        int n = s.length();
        return divide(s, 0, n - 1, k);
    }

    private int divide(String s, int left, int right, int k) {
        // 统计 子串s 所有字母的出现情况
        int[] freq = new int[26];
        for (int i = left; i <= right; i ++) {
            freq[s.charAt(i) - 'a'] ++;
        }
        // 找出不符合题意的字母
        char split = '?';
        for (int i = 0; i < 26; i ++) {
            if (freq[i] > 0 && freq[i] < k) {
                split = (char) (i + 'a');
                break ;
            }
        }

        // 没有更新过表示所有字母都满足题意
        if (split == '?') {
            return right - left + 1;
        }

        int i = left;
        int ret = 0;
        while (i <= right) {
            if (s.charAt(i) != split) {
                i ++;
                continue ;
            } else {
                // 左半段
                ret = divide(s, left, i - 1, k);

                while (i <= right && s.charAt(i) == split) {
                    i ++;
                }
                ret = Math.max(ret, divide(s, i, right, k));
            }
        }

        return ret;
    }
}
